package com.wzq.solution;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution89 {
    public List<Integer> grayCode(int n) {
        Map<Integer,Integer> m = new HashMap<Integer,Integer>();
        m.put(0,0);
        m.put(1,1);
        m.put(2,1);
        m.put(3,0);
        
        int rstSize = (int) Math.pow(2,n);
        List<Integer> rst = new ArrayList<Integer>(rstSize);
        
        for(int i=0;i<rstSize;i++){
            int gc = 0;
            for(int j=0;j<n;j++){
                int t = (int) Math.pow(2,j);
                int index = (i % (t*4))/t;
                gc = gc|m.get(index);
                    
            }
            
            rst.add(gc);
        }
        
        return rst;
        
    }
}